package 力扣._00周赛._415周赛.问题2;

import java.util.Arrays;

public class Solution {

    public long maxScore(int[] a, int[] b) {
        // 初始化负无穷小的动态规划数组
        int len = b.length;
        long[] dp0 = new long[len];
        long[] dp1 = new long[len];
        long[] dp2 = new long[len];
        long[] dp3 = new long[len];

        dp0[0] = (long) a[0] * b[0];
        for (int i = 1; i < len - 3; i++) {
            dp0[i] = Math.max(dp0[i - 1], (long) a[0] * b[i]);
        }
        dp1[1] = (long) a[1] * b[1] + dp0[0];
        for (int i = 2; i < len - 2; i++) {
            dp1[i] = Math.max(dp1[i - 1], (long) a[1] * b[i] + dp0[i - 1]);
        }
        dp2[2] = (long) a[2] * b[2] + dp1[1];
        for (int i = 3; i < len - 1; i++) {
            dp2[i] = Math.max(dp2[i - 1], (long) a[2] * b[i] + dp1[i - 1]);
        }
        dp3[3] = (long) a[3] * b[3] + dp2[2];
        for (int i = 4; i < len; i++) {
            dp3[i] = Math.max(dp3[i - 1], (long) a[3] * b[i] + dp2[i - 1]);
        }
        // dp3 中存储的就是最大得分
        return dp3[len - 1];
    }

    public static void main(String[] args) {
        System.out.println(new Solution().maxScore(
                new int[]{10, -9, -9, 10},
                new int[]{-4, 6, 6, 8, 0, 6, -4, 6, -6}
        ));

    }
}
